0784. 字母大小写全排列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

给定一个字符串 s，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合。以 任意顺序 返回输出。

---

示例 1：

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2：

输入: s = "3z4"
输出: ["3z4","3Z4"]

---

提示：

• 1 <= s.length <= 12
• s 由小写英文字母、大写英文字母和数字组成

2. 🎯 s.1 - 回溯

c

void dfs(char* s, int i, int n, char* path, char*** res, int* resSize) {
    if (i == n) {
        (*res)[*resSize] = (char*)malloc(n + 1);
        memcpy((*res)[*resSize], path, n + 1);
        (*resSize)++;
        return;
    }
    if (s[i] >= '0' && s[i] <= '9') {
        path[i] = s[i];
        dfs(s, i + 1, n, path, res, resSize);
    } else {
        path[i] = s[i] | 32; // lowercase
        dfs(s, i + 1, n, path, res, resSize);
        path[i] = s[i] & ~32; // uppercase
        dfs(s, i + 1, n, path, res, resSize);
    }
}

char** letterCasePermutation(char* s, int* returnSize) {
    int n = strlen(s);
    int maxSize = 1;
    for (int i = 0; i < n; i++) if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) maxSize *= 2;
    char** res = (char**)malloc(sizeof(char*) * maxSize);
    char* path = (char*)malloc(n + 1);
    path[n] = '\0';
    *returnSize = 0;
    dfs(s, 0, n, path, &res, returnSize);
    free(path);
    return res;
}

js

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function (s) {
  const res = []
  const dfs = (i, path) => {
    if (i === s.length) {
      res.push(path)
      return
    }
    const c = s[i]
    if (c >= '0' && c <= '9') {
      dfs(i + 1, path + c)
    } else {
      dfs(i + 1, path + c.toLowerCase())
      dfs(i + 1, path + c.toUpperCase())
    }
  }
  dfs(0, '')
  return res
}

py

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        res = []
        def dfs(i: int, path: list):
            if i == len(s):
                res.append(''.join(path))
                return
            c = s[i]
            if c.isdigit():
                path.append(c)
                dfs(i + 1, path)
                path.pop()
            else:
                path.append(c.lower())
                dfs(i + 1, path)
                path.pop()
                path.append(c.upper())
                dfs(i + 1, path)
                path.pop()
        dfs(0, [])
        return res

• 时间复杂度：$O(2^m\times n)$，其中 m 是字母个数，n 是字符串长度
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• 逐位处理，若是数字则直接添加，若是字母则分别尝试大小写两种情况
• 每个字母位产生两个分支，最终收集所有叶子节点